package Hot100;

import java.util.HashMap;

/**
 * @author zhangmin
 * @create 2021-12-20 11:02
 */
public class lengthOfLongestSubstring3 {

    /**
     * 3. 无重复字符的最长子串
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
     * 滑动窗口
     * */
    public int lengthOfLongestSubstring(String s) {
        //map记录每个字符在窗口中出现的次数
        HashMap<Character,Integer> window=new HashMap<>();
        int left=0,right=0;
        int res=0;
        while (right<s.length()){
            //c为要进入窗口的字符
            char c=s.charAt(right);
            right++;//此时窗口内元素为[left,right)
            //放入窗口
            window.put(c,window.getOrDefault(c,0)+1);
            while (window.get(c)>1){
                //需要左边窗口缩小
                char d=s.charAt(left);
                left++;
                window.put(d,window.getOrDefault(d,0)-1);
            }
            //此时窗口中元素没有重复
            res=Math.max(res,right-left);
        }
        return res;
    }


    //滑动窗口框架
    void slidingWindow(String s, String t) {
        //在s中找到包含t中所有元素的字串
        HashMap<Character,Integer> window=new HashMap<>();
        HashMap<Character,Integer> need=new HashMap<>();
        for (char c:t.toCharArray()) {
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left=0,right=0;
        //valid记录有多少字符是符合need要求的
        int valid=0;
        while (right<s.length()){
            // c 是将移入窗口的字符
            char c=s.charAt(right);
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新

            /*** debug 输出的位置 ***/
            System.out.println("window: ["+left+","+right+"]");

            // 判断左侧窗口是否要收缩
            while (window.get(c)>need.get(c)){
                // d 是将移出窗口的字符
                char d=s.charAt(left);
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新

            }
        }
    }

}
